
/**
 * 最大花费金额
 * 
 * 题目描述

双十一众多商品进行打折销售，小明想购买自己心仪的一些物品，但由于受购买资金限制，所以他决定从众多心仪商品中购买三件，而且想尽可能的花完资金。

现在请你设计一个程序帮助小明计算尽可能花费的最大资金数额。

输入描述
输入第一行为一维整型数组M，数组长度小于100，数组元素记录单个商品的价格，单个商品价格小于1000。
输入第二行为购买资金的额度R，R小于100000。
输入格式是正确的，无需考虑格式错误的情况。
输出描述
输出为满足上述条件的最大花费额度。
如果不存在满足上述条件的商品，请返回-1。
用例
输入	
23,26,36,27

78
输出	76
说明	金额23、26和27相加得到76，而且最接近且小于输入金额78。
输入	23,30,40
26
输出	-1
说明	因为输入的商品，无法组合出来满足三件之和小于26.故返回-1。

 * 
 */

import java.util.Arrays;
import java.util.Scanner;

/**
  * 
  题目解析
本题其实就是让我们从n个数中选择3个，保证这个3个数之和最接近且小于等于某个target。

解题思路是：

首先，我们将n个数的数组进行升序。

然后用三个指针I，L，R去指向数组的三个元素，形成三数组合，其中：

I指针就是按照for循环遍历的顺序进行移动，从0~n-1
L指针初始为 I + 1 位置
R指针初始为 n - 1 位置
如下图所示：



其中 I 指针在每一轮循环中是位置固定的，我们需要移动L，R来找不大于，且最接近target的组合。L，R指针的移动逻辑如下：

假设 sum = arr[I] + arr[L] + arr[R]
如果sum == target了，则说明当前三个指针指向的元素组合就是不大于，且最接近target的答案，可以直接返回。
如果 sum < target，则说明三指针指向元素组合之和是一个可能解，但是不一定是最优解，此时我们应该先记录这个可能解，然后尝试将L++，由于arr已经升序了，因此L++后，新的三数组合之和一定比现在的大。
如果 sum > target，则说明三指针指向元素组合之和过大了，此时应该R--，这样新的三数组合之和一定比现在的小。
按此逻辑，将当前 I 指针固定的数的三数组合情况全部求出。

之后，再 I ++ ，尝试其他三数组合。

  */
public class 最大花费金额 {
    
    public static void main(String[] args) {
        
        Scanner sc = new Scanner(System.in);
 
        int[] nums = Arrays.stream(sc.nextLine().split(",")).mapToInt(Integer::parseInt).toArray();
        int target = Integer.parseInt(sc.nextLine());
 
        System.out.println(solution(nums, target));
    }
 
    public static int solution(int[] nums, int target) {
        // 题目说小明要购买三件，如果商品不足三件直接返回-1
        if (nums.length < 3) return -1;
 
        // 数组升序
        Arrays.sort(nums);
 
        int ans = -1;
 
        for (int i = 0; i < nums.length; i++) {
            int l = i + 1;
            int r = nums.length - 1;
 
            while (l < r) {
                int sum = nums[i] + nums[l] + nums[r];
                if (sum == target) {
                    return sum;
                } else if (sum < target) {
                    ans = Math.max(ans, sum);
                    l++;
                } else {
                    r--;
                }
            }
        }
 
        return ans;
    }
    
}
